package com.leetcode.algorithm.y22.m06;

import java.util.HashMap;
import java.util.Map;

/**
 * 953. 验证外星语词典
 * 
 * https://leetcode.cn/problems/verifying-an-alien-dictionary/
 * 
 * @author jie.deng
 *
 */
class Question0953Solution01 {

	public boolean isAlienSorted(String[] words, String order) {
		Map<Character, Integer> orderMap = new HashMap<>();
		for (int i = 0; i < order.length(); i++) {
			orderMap.put(order.charAt(i), i);
		}
		for (int i = 0; i < words.length - 1; i++) {
			boolean flag = checkOrder(words[i], words[i + 1], orderMap);
			if (!flag) {
				return flag;
			}
		}
		return true;
	}

	private boolean checkOrder(String word1, String word2, Map<Character, Integer> orderMap) {
		int len1 = word1.length();
		int len2 = word2.length();
		for (int i = 0; i < Math.min(len1, len2); i++) {
			if (orderMap.get(word1.charAt(i)) > orderMap.get(word2.charAt(i))) {
				return false;
			} else if (orderMap.get(word1.charAt(i)) < orderMap.get(word2.charAt(i))) {
				return true;
			}
		}
		if (len1 <= len2) {
			return true;
		}
		return false;
	}

}